GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>EM-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">EM-Algorithmus</span></h1>

</header>

</div>

<p>Der <b>Erwartungs-Maximierungs-Algorithmus</b> (<span style="font-style:normal;font-weight:normal"><a href="Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic"><i>expectation-maximization algorithm</i></span>, daher auch <b>Expectation-Maximization-Algorithmus</b>, selten auch <i>Estimation-Maximization-Algorithmus</i>, kurz <b>EM-Algorithmus</b>) ist ein mathematischer <a href="Algorithmus" title="Algorithmus">Algorithmus</a>, ⁣⁣um iterativ (lokale) <a href="Maximum-Likelihood-Methode" title="Maximum-Likelihood-Methode">Maximum-Likelihood</a>- oder <a href="Maximum-a-posteriori-Sch%C3%A4tzung" title="Maximum-a-posteriori-Schätzung">Maximum-a-posteriori-Schätzungen</a> von Parametern in <a href="Statistik" title="Statistik">statistischen</a> Modellen zu finden.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Die Kernidee des EM-Algorithmus ist es, mit einem zufällig gewählten Modell zu starten, und abwechselnd die Zuordnung der Daten zu den einzelnen Teilen des Modells (<i>Erwartungsschritt</i>, kurz: <i>E-Schritt</i>) und die Parameter des Modells an die neueste Zuordnung (<i>Maximierungsschritt</i>, kurz: <i>M-Schritt</i>) zu verbessern. Im E-Schritt werden die Punkte besser zugeordnet, im M-Schritt wird das Modell so verändert, dass es besser zu den Daten passt. Findet keine wesentliche Verbesserung mehr statt, beendet man das Verfahren.

</p><p>Das Verfahren findet typischerweise nur „lokale“ Optima. Dadurch ist es oft notwendig, das Verfahren mehrfach aufzurufen und das beste so gefundene Ergebnis auszuwählen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Mathematische_Formulierung">Mathematische Formulierung</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Funktionsweise">Funktionsweise</h3></div>

<p>Es liegen Objekte mit einer gewissen Anzahl von Eigenschaften vor. Die Eigenschaften nehmen zufällige Werte an. Einige Eigenschaften können gemessen werden, andere jedoch nicht. Formal gesehen sind die Objekte Instanzen einer mehrdimensionalen <a href="Zufallsvariable" title="Zufallsvariable">Zufallsvariablen</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span>, die einer unbekannten <a href="Wahrscheinlichkeitsverteilung" class="mw-redirect" title="Wahrscheinlichkeitsverteilung">Wahrscheinlichkeitsverteilung</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(x)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8cb7afced134ef75572e5314a5d278c2d644f438.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:4.398ex; height:2.843ex;" alt="{\displaystyle p(x)}" loading="lazy"></span> unterliegt; einige Dimensionen sind „beobachtbar“, andere sind „versteckt“. Ziel ist es, die unbekannte Wahrscheinlichkeitsverteilung zu bestimmen.

</p><p>Zunächst nimmt man an, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(x)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8cb7afced134ef75572e5314a5d278c2d644f438.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:4.398ex; height:2.843ex;" alt="{\displaystyle p(x)}" loading="lazy"></span> sei bis auf einige Parameter bekannt. Meist wählt man <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"></span> als <a href="Mischverteilung" title="Mischverteilung">Mischverteilung</a>, also als gewichtete Summe von so vielen Standardverteilungen, wie beobachtbare Eigenschaften vorliegen. Wählt man beispielsweise als Standardverteilung die <a href="Normalverteilung" title="Normalverteilung">Normalverteilung</a>, so sind die unbekannten Parameter jeweils der <a href="Erwartungswert" title="Erwartungswert">Erwartungswert</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"></span> und die <a href="Varianz_(Stochastik)" title="Varianz (Stochastik)">Varianz</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sigma ^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53a5c55e536acf250c1d3e0f754be5692b843ef5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.385ex; height:2.676ex;" alt="{\displaystyle \sigma ^{2}}" loading="lazy"></span>. Ziel ist es nun, die Parameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc927b19f46d005b4720db7a0f96cd5b6f1a0d9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \Theta }" loading="lazy"></span> der vermuteten Wahrscheinlichkeitsverteilung zu bestimmen. Wählt man eine Mischverteilung, so enthält <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc927b19f46d005b4720db7a0f96cd5b6f1a0d9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \Theta }" loading="lazy"></span> auch die Gewichtungsfaktoren der Summe.

</p><p>Für gewöhnlich geht man ein solches Problem mit der <a href="Maximum-Likelihood-Methode" title="Maximum-Likelihood-Methode">Maximum-Likelihood-Methode</a> an. Dies ist hier jedoch nicht möglich, da die gesuchten Parameter von den versteckten Eigenschaften abhängen – und diese sind unbekannt. Um trotzdem zum Ziel zu kommen, wird also eine Methode benötigt, die mit den gesuchten Endparametern die versteckten Eigenschaften schätzt. Diese Aufgabe erfüllt der EM-Algorithmus.

</p><p>Der EM-Algorithmus arbeitet <a href="Iteration" title="Iteration">iterativ</a> und führt in jedem Durchgang zwei Schritte aus:

</p>

<ol><li>E-Schritt: Versteckte Eigenschaften <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"></span> schätzen. Zunächst werden die versteckten Eigenschaften aus den im vorherigen Durchgang bestimmten Endparametern <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc927b19f46d005b4720db7a0f96cd5b6f1a0d9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \Theta }" loading="lazy"></span> und den beobachteten Daten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> geschätzt. Dazu wird die sogenannte Q-Funktion verwendet, die einen vorläufigen Erwartungswert der gesuchten Verteilung berechnet.</li>

<li>M-Schritt: Endparameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc927b19f46d005b4720db7a0f96cd5b6f1a0d9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \Theta }" loading="lazy"></span> bestimmen. Jetzt, wo die versteckten Eigenschaften abgeschätzt sind, wird die Maximum-Likelihood-Methode angewandt, um die eigentlich gesuchten Parameter zu bestimmen.</li></ol>

<p>Der Algorithmus endet, wenn sich die bestimmten Parameter nicht mehr wesentlich ändern.

</p><p>Bewiesenermaßen konvergiert die Folge der bestimmten <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Theta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Theta }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc927b19f46d005b4720db7a0f96cd5b6f1a0d9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \Theta }" loading="lazy"></span>, das heißt, der Algorithmus terminiert auf jeden Fall. Allerdings bildet das Ergebnis meist nur ein lokales Optimum, welches zwar gut, aber nicht unbedingt optimal ist. Es ist daher nötig den Algorithmus mit vielen unterschiedlichen Startwerten auszuführen, um ein Endergebnis möglichst nah am Optimum zu finden.

</p>

<div class="mw-heading mw-heading3"><h3 id="Formulierung_als_Zufallsexperiment">Formulierung als Zufallsexperiment</h3></div>

<p>Rein formal wird beim EM-Algorithmus angenommen, dass die Werte der beobachteten stochastischen Größe auf folgende Art und Weise zustande kommen:

Wähle zuerst eine der eingehenden Zufallsvariablen aus und übernimm deren Wert als Endergebnis. Das bedeutet, dass genau ein Gewicht den Wert eins annimmt und alle anderen null sind. Bei der Approximation der Gewichte durch den EM-Algorithmus ist dies normalerweise aber nicht mehr der Fall. Die <a href="Wahrscheinlichkeitsdichte" class="mw-redirect" title="Wahrscheinlichkeitsdichte">Wahrscheinlichkeitsdichte</a> eines Zielwertes lässt sich bei <a href="Normalverteilung" title="Normalverteilung">Normalverteilungsannahme</a> und konstanter Varianz der einzelnen Zufallsvariablen darstellen als:

</p>

<msub>

</mrow>

</msub>

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p(y_{i}\mid h)={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}\operatorname {exp} \left(-{\frac {1}{2\sigma ^{2}}}\sum _{j=1}^{n}w_{ij}(y_{i}-\mu _{j})^{2}\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eb8ca009d5be1a78dd0ed64bb919fe6693f0adaa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; margin-left: -0.089ex; width:50.07ex; height:7.676ex;" alt="{\displaystyle p(y_{i}\mid h)={\frac {1}{\sqrt {2\pi \sigma ^{2}}}}\operatorname {exp} \left(-{\frac {1}{2\sigma ^{2}}}\sum _{j=1}^{n}w_{ij}(y_{i}-\mu _{j})^{2}\right)}" loading="lazy"></span></dd></dl>

<p>Dabei besitzen die verwendeten Bezeichnungen folgende Bedeutungen:

</p>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle w_{ij}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d3302ff355269436b43bc2fbe180303881c09321.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.141ex; height:2.343ex;" alt="{\displaystyle w_{ij}}" loading="lazy"></span>: Gewicht der <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"></span>-ten Zufallsvariable für den <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-ten Wert der Zielgröße</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>: Anzahl der Gewichte</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67d30d30b6c2dbe4d6f150d699de040937ecc95f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.009ex;" alt="{\displaystyle y_{i}}" loading="lazy"></span>: Wert der <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-ten Zielgröße</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span>: Stichprobe</li>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{j}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b2800dcde32ff75ad8aecdf9c4c4e2d7fad58db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.311ex; height:2.343ex;" alt="{\displaystyle \mu _{j}}" loading="lazy"></span>: Erwartungswert der <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"></span>-ten Zufallsvariable</li>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma ^{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53a5c55e536acf250c1d3e0f754be5692b843ef5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.385ex; height:2.676ex;" alt="{\displaystyle \sigma ^{2}}" loading="lazy"></span>: Varianz</li></ul>

<div class="mw-heading mw-heading2"><h2 id="EM-Clustering">EM-Clustering</h2></div>

<p>Das <b>EM-Clustering</b> ist ein Verfahren zur <a href="Clusteranalyse" title="Clusteranalyse">Clusteranalyse</a>, das die Daten mit einem <a href="Mischverteilung#Häufiger_Spezialfall:_Gaußsche_Mischmodelle" title="Mischverteilung">Gaußschen Mischmodell</a> (<span style="font-style:normal;font-weight:normal"><a href="Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic"><i>gaussian mixture model</i></span>, kurz: <i>GMM</i>) – also als Überlagerung von Normalverteilungen – repräsentiert. Dieses Modell wird zufällig oder heuristisch initialisiert und anschließend mit dem allgemeinen EM-Prinzip verfeinert.

</p><p>Das EM-Clustering besteht aus mehreren <a href="Iteration" title="Iteration">Iterationen</a> der Schritte <i>Erwartung</i> und <i>Maximierung</i>.

</p>

<ul><li>Im Initialisierungs-Schritt muss das <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"></span> frei gewählt werden. Nimm dazu an, dass genau eine beliebige Zufallsvariable (genau eine beliebige Trainingsinstanz <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{k}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4b2ab0248723a410cc2c67ce06ad5c043dcbb933.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.228ex; height:2.009ex;" alt="{\displaystyle y_{k}}" loading="lazy"></span>) diesem Erwartungswert <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9fd47b2a39f7a7856952afec1f1db72c67af6161.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.402ex; height:2.176ex;" alt="{\displaystyle \mu }" loading="lazy"></span> entspricht, d. h. setze <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{1,\mathrm {appr} }=y_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{1,\mathrm {appr} }=y_{k}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/187839058b655a89b5bf9e38d7b5485f3489dc34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:11.534ex; height:2.343ex;" alt="{\displaystyle \mu _{1,\mathrm {appr} }=y_{k}}" loading="lazy"></span>.</li>

<li>Im Erwartungsschritt werden die Erwartungswerte der Gewichte berechnet unter der Annahme, dass die Erwartungswerte der eingehenden Zufallsvariablen den im Maximierungsschritt berechneten entsprechen. Dies ist allerdings nur möglich, falls es sich nicht um die erste Iteration handelt. <br> Die Erwartungswerte lassen sich darstellen als <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \operatorname {E} [w_{ij}]=p(X_{j}=y_{i}|\mu _{j}=\mu _{j,\mathrm {appr} })/\sum _{k=1}^{n}p(X_{k}=y_{i}\mid \mu _{k}=\mu _{k,\mathrm {appr} })}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {E} [w_{ij}]=p(X_{j}=y_{i}|\mu _{j}=\mu _{j,\mathrm {appr} })/\sum _{k=1}^{n}p(X_{k}=y_{i}\mid \mu _{k}=\mu _{k,\mathrm {appr} })}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5fac546501e0e22454e17128fe02806e7cbb637e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:62.175ex; height:6.843ex;" alt="{\displaystyle \operatorname {E} [w_{ij}]=p(X_{j}=y_{i}|\mu _{j}=\mu _{j,\mathrm {appr} })/\sum _{k=1}^{n}p(X_{k}=y_{i}\mid \mu _{k}=\mu _{k,\mathrm {appr} })}" loading="lazy"></span></li>

<li>Im Maximierungsschritt werden die Erwartungswerte der Wahrscheinlichkeitsverteilungen der einzelnen Zufallsvariablen bestimmt, bei denen die Wahrscheinlichkeit für das Eintreffen des Stichprobenergebnisses maximiert wird. Dies geschieht unter der Annahme, dass die exakten Werte der Gewichte jeweils ihren Erwartungswerten entsprechen (<a href="Maximum-Likelihood-Algorithmus" class="mw-redirect" title="Maximum-Likelihood-Algorithmus">Maximum-Likelihood-Algorithmus</a>). Die auf diese Weise geschätzten Erwartungswerte ergeben sich bei Normalverteilungsannahme durch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{j,\mathrm {appr} }={\frac {\sum _{i=1}^{N}\operatorname {E} [w_{ij}]y_{i}}{\sum _{i=1}^{N}\operatorname {E} [w_{ij}]}}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{j,\mathrm {appr} }={\frac {\sum _{i=1}^{N}\operatorname {E} [w_{ij}]y_{i}}{\sum _{i=1}^{N}\operatorname {E} [w_{ij}]}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f6dc3d49a26acfa065331620547844c3e5a19aea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:23.696ex; height:7.509ex;" alt="{\displaystyle \mu _{j,\mathrm {appr} }={\frac {\sum _{i=1}^{N}\operatorname {E} [w_{ij}]y_{i}}{\sum _{i=1}^{N}\operatorname {E} [w_{ij}]}}}" loading="lazy"></span></li></ul>

<dl><dd>wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> die Größe des Trainingsdatensatzes bezeichnet.</dd></dl>

<ul><li>Durch Wiederholung der Erwartungs- und Maximierungsschritte werden die Parameter ihren tatsächlichen Werten weiter angenähert.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Vorteile_des_EM-Clusterings">Vorteile des EM-Clusterings</h3></div>

<ul><li>Mathematisches Modell der Daten mit Normalverteilungen</li>

<li>Erlaubt Cluster unterschiedlicher Größe (im Sinne von Streuung – k-Means ignoriert die Varianz der Cluster).</li>

<li>Kann <a href="Korrelation" title="Korrelation">korrelierte</a> Cluster erkennen und repräsentieren durch die <a href="Kovarianzmatrix" title="Kovarianzmatrix">Kovarianzmatrix</a></li>

<li>Kann mit unvollständigen Beobachtungen umgehen</li></ul>

<div class="mw-heading mw-heading2"><h2 id="K-Means_als_EM-Verfahren">K-Means als EM-Verfahren</h2></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="K-Means-Algorithmus" title="K-Means-Algorithmus">k-Means-Algorithmus</a></i></div>

<p>Auch der k-Means-Algorithmus kann als EM-Algorithmus verstanden werden, der die Daten als <a href="Voronoi-Diagramm" title="Voronoi-Diagramm">Voronoi-Zellen</a> modelliert.

</p><p>Eine EM-Variante des k-Means-Algorithmus sieht wie folgt aus:

</p>

<ul><li>Im Initialisierungs-Schritt werden die Clusterzentren <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dea0a0293841cce9eef98b55e53a92b82ae59ee4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.201ex; height:2.176ex;" alt="{\displaystyle \mu _{i}}" loading="lazy"></span> zufällig oder mit einer Heuristik gewählt.</li>

<li>Im Erwartungsschritt werden Datenobjekte ihrem nächsten Clusterzentrum zugeordnet, d. h.</li></ul>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>falls</mtext>

</mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</munder>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>sonst.</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \operatorname {E} [w_{ij}]={\begin{cases}1,&{\text{falls}}\quad ||\mu _{i}-X_{j}||=\min _{i}{||\mu _{i}-X_{j}||}\\0,&{\text{sonst.}}\end{cases}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/79c9d29f36ed14b252d1995d0f3129e91a57b8d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:51.236ex; height:6.176ex;" alt="{\displaystyle \operatorname {E} [w_{ij}]={\begin{cases}1,&{\text{falls}}\quad ||\mu _{i}-X_{j}||=\min _{i}{||\mu _{i}-X_{j}||}\\0,&{\text{sonst.}}\end{cases}}}" loading="lazy"></span></dd></dl>

<ul><li>Im Maximierungsschritt werden die Clusterzentren neu berechnet als Mittelwert der ihnen zugeordneten Datenpunkte:<br><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{j}={\frac {1}{\sum _{i}^{n}\operatorname {E} [w_{ij}]}}\sum _{i=1}^{n}\operatorname {E} [w_{ij}]y_{i}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{j}={\frac {1}{\sum _{i}^{n}\operatorname {E} [w_{ij}]}}\sum _{i=1}^{n}\operatorname {E} [w_{ij}]y_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2234cdd53ea6337434431c6e82207f81cc60a853.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:28.409ex; height:6.843ex;" alt="{\displaystyle \mu _{j}={\frac {1}{\sum _{i}^{n}\operatorname {E} [w_{ij}]}}\sum _{i=1}^{n}\operatorname {E} [w_{ij}]y_{i}}" loading="lazy"></span></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weitere_Instanzen_des_EM-Algorithmus">Weitere Instanzen des EM-Algorithmus</h2></div>

<ul><li><a href="Mischverteilung#Parameterschätzung" title="Mischverteilung">Schätzen der Parameter einer Mischverteilung</a></li>

<li><a href="Baum-Welch-Algorithmus" title="Baum-Welch-Algorithmus">Baum-Welch-Algorithmus</a> zum Schätzen der Parameter eines <a href="Hidden_Markov_Model" title="Hidden Markov Model">Hidden Markov Modells</a></li>

<li>Lernen eines <a href="Bayes%E2%80%99sches_Netz" class="mw-redirect" title="Bayes’sches Netz">Bayes’schen Netzes</a> mit versteckten Variablen</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Beweis_für_den_Maximierungsschritt_bei_Normalverteilungsannahme"><span id="Beweis_f.C3.BCr_den_Maximierungsschritt_bei_Normalverteilungsannahme"></span>Beweis für den Maximierungsschritt bei Normalverteilungsannahme</h2></div>

<p>Bewiesen werden soll:

</mrow>

<msub>

</mrow>

</msub>

</munder>

</mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\underset {\mu _{k}}{\mathrm {arg\,max} }}\prod _{i=1}^{m}P\left(y\mid h\right)={\frac {1}{m}}\sum _{i=1}^{m}{\frac {1}{2\sigma ^{2}}}\operatorname {E} [w_{ik}]y_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6903788c68a5c332c8b7eb9c44afc49e99f8e2ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:43.077ex; height:6.843ex;" alt="{\displaystyle {\underset {\mu _{k}}{\mathrm {arg\,max} }}\prod _{i=1}^{m}P\left(y\mid h\right)={\frac {1}{m}}\sum _{i=1}^{m}{\frac {1}{2\sigma ^{2}}}\operatorname {E} [w_{ik}]y_{i}}" loading="lazy"></span>

</p><p>Anstatt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(y\mid h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(y\mid h)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5ca8f81611fabd957b6dc221cd46595781264eda.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.986ex; height:2.843ex;" alt="{\displaystyle P(y\mid h)}" loading="lazy"></span> zu maximieren, kann auch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ln P(y\mid h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ln P(y\mid h)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffbfcad4eaa39b69db5094d661dc6b940301e3bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.313ex; height:2.843ex;" alt="{\displaystyle \ln P(y\mid h)}" loading="lazy"></span> maximiert werden, da der <a href="Logarithmus" title="Logarithmus">Logarithmus</a> eine streng monoton steigende Funktion ist.

</p>

<table>

</mrow>

</munder>

</mrow>

</mrow>

</mrow>

</munderover>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\underset {\mu }{\mathrm {arg\,max} }}\ln \prod _{i=1}^{m}P(y\mid h)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1842ff75e8d92d50366ad3fb91de7067a5d2129d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:22.006ex; height:6.843ex;" alt="{\displaystyle {\underset {\mu }{\mathrm {arg\,max} }}\ln \prod _{i=1}^{m}P(y\mid h)}" loading="lazy"></span>

</td>

</mrow>

</munder>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ={\underset {\mu }{\mathrm {arg\,max} }}\left(\sum _{i=1}^{m}\left(\ln {\frac {1}{\sqrt {2\pi \sigma ^{2}}}}-\sum _{j=1}^{n}{\frac {1}{2\sigma ^{2}}}\operatorname {E} [w_{ij}](y_{i}-\mu _{j})^{2}\right)\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/594ef731bcc4c78bd88cc004f452ae0fa6a37333.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:59.197ex; height:7.676ex;" alt="{\displaystyle ={\underset {\mu }{\mathrm {arg\,max} }}\left(\sum _{i=1}^{m}\left(\ln {\frac {1}{\sqrt {2\pi \sigma ^{2}}}}-\sum _{j=1}^{n}{\frac {1}{2\sigma ^{2}}}\operatorname {E} [w_{ij}](y_{i}-\mu _{j})^{2}\right)\right)}" loading="lazy"></span>

</td></tr>

<tr>

<td>

</td>

</mrow>

</munder>

</mrow>

<mrow>

<mrow>

<mfrac>

<msqrt>

<msup>

</mrow>

</msup>

</msqrt>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ={\underset {\mu }{\mathrm {arg\,max} }}\left(m\ln {\frac {1}{\sqrt {2\pi \sigma ^{2}}}}-{\frac {1}{2\sigma ^{2}}}\sum _{i=1}^{m}\sum _{j=1}^{n}\operatorname {E} [w_{ij}](y_{i}-\mu _{j})^{2}\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a6966de75a24c09cfd5d833c48141dec3d099ea3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:57.943ex; height:7.676ex;" alt="{\displaystyle ={\underset {\mu }{\mathrm {arg\,max} }}\left(m\ln {\frac {1}{\sqrt {2\pi \sigma ^{2}}}}-{\frac {1}{2\sigma ^{2}}}\sum _{i=1}^{m}\sum _{j=1}^{n}\operatorname {E} [w_{ij}](y_{i}-\mu _{j})^{2}\right)}" loading="lazy"></span>.

</td></tr></tbody></table>

<p>Der Minuend ist eine Konstante, deswegen ist es ausreichend, den Subtrahend zu minimieren:

</p>

</mrow>

</munder>

</mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msup>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\underset {\mu }{\mathrm {arg\,min} }}\left({\frac {1}{2\sigma ^{2}}}\sum _{i=1}^{m}\sum _{j=1}^{n}\operatorname {E} \left[w_{ij}\right]\left(y_{i}-\mu _{j}\right)^{2}\right)=}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/aec20840126575abd76ee950f07df49e1d5b614f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:42.247ex; height:7.676ex;" alt="{\displaystyle {\underset {\mu }{\mathrm {arg\,min} }}\left({\frac {1}{2\sigma ^{2}}}\sum _{i=1}^{m}\sum _{j=1}^{n}\operatorname {E} \left[w_{ij}\right]\left(y_{i}-\mu _{j}\right)^{2}\right)=}" loading="lazy"></span></dd>

</mrow>

</munder>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\underset {\mu }{\mathrm {arg\,min} }}\left(\sum _{i=1}^{m}\sum _{j=1}^{n}\operatorname {E} [w_{ij}](y_{i}-\mu _{j})^{2}\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c0c8b865537a29e9f11003215149b54906ea90ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:35.023ex; height:7.676ex;" alt="{\displaystyle {\underset {\mu }{\mathrm {arg\,min} }}\left(\sum _{i=1}^{m}\sum _{j=1}^{n}\operatorname {E} [w_{ij}](y_{i}-\mu _{j})^{2}\right)}" loading="lazy"></span>.</dd></dl>

<p>Eine quadratische Summe ergibt stets einen nichtnegativen Wert. Daher ist das absolute Minimum durch 0 beschränkt und somit auch ein lokales Minimum.

Man setze die 1. Ableitung für diesen Term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy"></span> nach jedem <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{k}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/25f9c464114cfcd7e31e53de202703377b7c5ffb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.49ex; height:2.176ex;" alt="{\displaystyle \mu _{k}}" loading="lazy"></span> auf 0

</p>

<mfrac>

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\mathrm {d} t}{\mathrm {d} \mu _{k}}}=-2\sum _{i=1}^{m}\operatorname {E} \left[w_{ik}\right]\left(y_{i}-\mu _{k}\right)=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/67cd4be98621735cb4477d4c7a2662b6f8c5514c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:34.741ex; height:6.843ex;" alt="{\displaystyle {\frac {\mathrm {d} t}{\mathrm {d} \mu _{k}}}=-2\sum _{i=1}^{m}\operatorname {E} \left[w_{ik}\right]\left(y_{i}-\mu _{k}\right)=0}" loading="lazy"></span>,</dd></dl>

<p>denn die Ableitung aller Summanden der Summe über <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"></span> sind <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span>, außer für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b954ae5b92d2350b5af4f8d1b0e91d26a01bbe70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:5.294ex; height:2.509ex;" alt="{\displaystyle j=k}" loading="lazy"></span>. Folglich:

</p>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mrow>

</munderover>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{m}\operatorname {E} [w_{ik}]y_{i}=\mu _{k}\sum _{i=1}^{m}\operatorname {E} [w_{ik}]\quad \Rightarrow \quad \mu _{k}={\frac {\sum _{i=1}^{m}\operatorname {E} \left[w_{ik}\right]y_{i}}{\sum _{i=1}^{m}\operatorname {E} [w_{ik}]}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d5c64e08ed3c70e61f45fb0865a85a7ad13b1301.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:56.354ex; height:7.009ex;" alt="{\displaystyle \sum _{i=1}^{m}\operatorname {E} [w_{ik}]y_{i}=\mu _{k}\sum _{i=1}^{m}\operatorname {E} [w_{ik}]\quad \Rightarrow \quad \mu _{k}={\frac {\sum _{i=1}^{m}\operatorname {E} \left[w_{ik}\right]y_{i}}{\sum _{i=1}^{m}\operatorname {E} [w_{ik}]}}}" loading="lazy"></span>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup></dd></dl>

<p>q. e. d.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Arthur_P._Dempster" title="Arthur P. Dempster">A. P. Dempster</a>, N. M. Laird, D. B. Rubin: <i>Maximum-Likelihood from incomplete data via the EM algorithm.</i> In: <i>Journal of the Royal Statistical Society.</i> 1977, S. 1–38 <a href="JSTOR" title="JSTOR">JSTOR</a>:<a rel="nofollow" class="external text" href="http://www.jstor.org/stable/2984875">2984875</a>.</li>

<li>Tom M. Mitchell: <i>Machine Learning</i>. The Mc-Graw-Hill Companies, 1997.</li>

<li>Richard O. Duda u. a.: <i>Pattern Classification.</i> 2. Auflage. John Wiley & Sons, New York 2012.</li>

<li><a href="Stuart_Russell" title="Stuart Russell">Stuart Russell</a>, <a href="Peter_Norvig" title="Peter Norvig">Peter Norvig</a>: <i><a rel="nofollow" class="external text" href="http://aima.cs.berkeley.edu/">Artificial Intelligence: A Modern Approach</a>.</i> 2. Auflage. Prentice Hall, 2002.</li>

<li>Stuart Russell, Peter Norvig: <i><a rel="nofollow" class="external text" href="http://aima.cs.berkeley.edu/">Künstliche Intelligenz: Ein moderner Ansatz</a>.</i> Pearson Studium, 2004, ISBN 3-8273-7089-2. (deutsche Übersetzung der 2. Auflage)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Xiao-Li Meng, David Van Dyk: <cite style="font-style:italic">The EM Algorithm—an Old Folk-song Sung to a Fast New Tune</cite>. In: <cite style="font-style:italic">Journal of the Royal Statistical Society Series B: Statistical Methodology</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>59</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>3</span>, 1. September 1997, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%221369-7412%22&key=cql">1369-7412</a></span>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>511–567</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1111/1467-9868.00082">10.1111/1467-9868.00082</a></span> (<a rel="nofollow" class="external text" href="https://academic.oup.com/jrsssb/article/59/3/511/7083070">oup.com</a> [abgerufen am 12. Februar 2024]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:EM-Algorithmus&rft.atitle=The+EM+Algorithm%E2%80%94an+Old+Folk-song+Sung+to+a+Fast+New+Tune&rft.au=Xiao-Li+Meng%2C+David+Van+Dyk&rft.date=1997-09-01&rft.doi=10.1111%2F1467-9868.00082&rft.genre=journal&rft.issn=1369-7412&rft.issue=3&rft.jtitle=Journal+of+the+Royal+Statistical+Society+Series+B%3A+Statistical+Methodology&rft.pages=511-567&rft.volume=59" style="display:none"> </span></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text"><cite style="font-style:italic">Examples of the EM Algorithm</cite>. In: <cite style="font-style:italic">The EM Algorithm and Extensions</cite>. John Wiley & Sons, Ltd, 2008, ISBN 978-0-470-19161-3, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>41–75</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1002/9780470191613.ch2">10.1002/9780470191613.ch2</a></span> (<a rel="nofollow" class="external text" href="https://onlinelibrary.wiley.com/doi/abs/10.1002/9780470191613.ch2">wiley.com</a> [abgerufen am 31. Januar 2021]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:EM-Algorithmus&rft.atitle=Examples+of+the+EM+Algorithm&rft.btitle=The+EM+Algorithm+and+Extensions&rft.date=2008&rft.doi=10.1002%2F9780470191613.ch2&rft.genre=book&rft.isbn=9780470191613&rft.pages=41-75&rft.pub=John+Wiley+%26+Sons%2C+Ltd" style="display:none"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-12-19" href="https://de.wikipedia.org/wiki/?title=EM-Algorithmus&oldid=251372477">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>